#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 100010;
const int maxm = maxn * 20;
const int inf = 1e9;

struct node {
  ll cnt, sum;
  node() { cnt = sum =0; }
  node(ll x, ll y) { cnt = x, sum = y; }
  friend node operator+(node x, node y) {
    return node(x.cnt + y.cnt, x.sum + y.sum);
  }
  friend node operator-(node x, node y) {
    return node(x.cnt - y.cnt, x.sum - y.sum);
  }
};

struct info {
  int j, l, r;
  info() { j = l = r = 0; }
  info(int x, int y, int z) { j = x, l = y, r = z; }
} d[maxn];

struct SegTree {
  node t[maxm];
  int rt[maxn], ls[maxm], rs[maxm], tot;
  
  #define mid ((l + r) >> 1)
  
  void upd(int &p, int q, int l, int r, int x, int v) {
    p = ++tot, ls[p] = ls[q], rs[p] = rs[q];
    if (l == r) return t[p] = t[q] + node(1, v), void();
    if (x <= mid) upd(ls[p], ls[q], l, mid, x, v);
    else if (x > mid) upd(rs[p], rs[q], mid + 1, r, x, v);
    t[p] = t[ls[p]] + t[rs[p]];
  }
  
  node qry(int p, int l, int r, int x, int y) {
    if (x > y) return node(0, 0);
    if (l == x && r == y) return t[p];
    if (y <= mid) return qry(ls[p], l, mid, x, y);
    else if (x > mid) return qry(rs[p], mid + 1, r, x, y);
    else return qry(ls[p], l, mid, x, mid) + qry(rs[p], mid + 1, r, mid + 1, y);
  }
  
  #undef mid
} t1, t2;

int n, q, hd, tl;
ll dp[maxn];
pii a[maxn];
vector<int> vl[maxn], vr[maxn];

ll cost(int l, int r) {
  node tmp;
  ll res = 0;
  res += t1.qry(t1.rt[l], 1, n, r, n).cnt;
  tmp = t1.qry(t1.rt[n], 1, n, 1, r) - t1.qry(t1.rt[l - 1], 1, n, 1, r);
  res += tmp.cnt * r - tmp.sum;
  tmp = t2.qry(t2.rt[1], 1, n, l, n) - t2.qry(t2.rt[r + 1], 1, n, l, n);
  res += tmp.sum - tmp.cnt * l;
  int mid = (l + r) >> 1;
  tmp = t1.qry(t1.rt[l - 1], 1, n, l, mid);
  res += tmp.sum - tmp.cnt * l;
  tmp = t1.qry(t1.rt[l - 1], 1, n, mid + 1, r);
  res += tmp.cnt * r - tmp.sum;
  tmp = t2.qry(t2.rt[r + 1], 1, n, l, mid);
  res += tmp.sum - tmp.cnt * l;
  tmp = t2.qry(t2.rt[r + 1], 1, n, mid + 1, r);
  res += tmp.cnt * r - tmp.sum;
  return res;
}

ll val(int x, int y) {
  return dp[x] + cost(x, y);
}

int main() {
  freopen("block.in", "r", stdin);
  freopen("block.out", "w", stdout);
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> q;
  rep (i, 1, q) {
    int l, r;
    cin >> l >> r, a[i] = pii(l, r);
    vl[l].emplace_back(r);
    vr[r].emplace_back(l);
  }
  rep (i, 1, n) {
    t1.rt[i] = t1.rt[i - 1];
    for (int x : vl[i]) t1.upd(t1.rt[i], t1.rt[i], 1, n, x, x);
  }
  per (i, n, 1) {
    t2.rt[i] = t2.rt[i + 1];
    for (int x : vr[i]) t2.upd(t2.rt[i], t2.rt[i], 1, n, x, x);
  }
  rep (i, 1, n) dp[i] = inf;
  dp[1] = 0, d[hd = tl = 1] = info(1, 2, n);
  rep (i, 2, n) {
		while (hd < tl && d[hd].r < i) hd++;
		int j = d[hd].j;
		d[hd].l = i, dp[i] = dp[j] + cost(j, i);
		while (hd < tl && val(i, d[tl].l) <= val(d[tl].j, d[tl].l)) tl--;
		int l = d[tl].l, r = d[tl].r + 1;
		while (l < r) {
		  int mid = (l + r) >> 1;
		  if (val(i, mid) <= val(d[tl].j, mid)) r = mid;
		  else l = mid + 1;
		}
		if (l <= n) d[tl].r = l - 1, d[++tl] = info(i, l, n);
  }
  cout << dp[n] << '\n';
}